#include <stdio.h>

int main()
{
    int nums[] = {
        1,
        0,
        9,
        8,
        2,
        5,
        6,
    };
    int numSize = 7;
    for (int i = 1; i < numSize; i++) //开始的时候第一个数字为有序数组
    {
        int left = 0;
        int right = i - 1; //二分法边界
        int temp = nums[i];

        while (left <= right) //即退出条件是right<left
        {
            int mid = (left + right) / 2;
            if (nums[mid] > temp)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= right + 1; j--) //由高处往后挪位
        {
            nums[j + 1] = nums[j];
        }
        nums[right + 1] = temp;
    }
    for (int i = 0; i < numSize; i++)
    {
        printf("%d ", nums[i]);
    }
}